package com.majie.algorithm.sort;

import com.majie.common.SwapUtils;

/**
 * 两路快速排序
 * <p>
 * 时间复杂度:
 * 数组刚好是有序的,正序或者逆序,最坏情况为O(n^2)
 * 平均是O(nlogn)
 *
 * @author majie
 * @date 2018-05-07
 */
public class QuickSort2 {

    public QuickSort2( ) {
    }

    /**
     * 排序
     * <p>
     * 1.找到零界点
     * 2.分别对零界点左右递归
     * 3.最后交换临界点和最左边
     */
    private static void sort(int[] arr, int left, int right) {


        //递归的边界条件
        if (left >= right) {
            return;
        }

        int point = partition(arr, left, right);
        sort(arr, left, point - 1);
        sort(arr, point + 1, right);

    }

    /**
     * 找到临界点
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] arr, int left, int right) {

        int v = arr[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < v) {
                j++;
                SwapUtils.swap(arr, i, j);
            }
        }
        SwapUtils.swap(arr, left, j);
        return j;
    }


    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {10, 6, 8, 3, 6, 5, 9, 4, 3, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
